/*
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).
*/

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        int slen = L.size(), wlen = L[0].size();
        vector<int> result;
        if (!S.length()) return result;
        // create word map
        unordered_map<string, int> wmap;
        for (auto it = L.begin(); it != L.end(); it++) wmap[*it] ++;
        for (int i = 0; i + slen*wlen <= S.length(); i++) {
            int j = 0;
            unordered_map<string, int> curmap;
            for (; j < slen; j++) {
                string w = S.substr(i+j*wlen, wlen);
                if (wmap.find(w) == wmap.end()) break;
                curmap[w] ++;
                if (curmap[w] > wmap[w]) break;
            }
            if (j==slen) result.push_back(i);
        }
        return result;
    }
};
